#include "types.h"
#include "comm.h"
#include "primitives.h"

#include "../util/macros.h"
#include "../matrix/matrix.h"
#include "../image/image.h"
#include "../util/quicksort.h"
#include "../image/drawing/imdraw.h"

Point point2d_new( double x, double y  ) {
	
}

Vertex * vertex_new(void) {
	Vertex * v;
	v = imp_alloc(Vertex);
	return v;
}

Vertex * vertex_new_copy(Vertex * v) {
	Vertex * copy;

	copy = vertex_new();
	*copy = *v;

	return copy;
}

void vertex_delete(Vertex * v) {
	imp_free(v);
}

VertexList * vertex_list_new(void) {

	VertexList * VL;
	VL = imp_alloc(VertexList);
	return VL;
}

void vertex_list_add(VertexList * VL, Vertex * p) {

	_verify(VL);
	_verify(p);

	if (VL->first) {

		p->next = VL->first;
		p->prev = VL->last;
		VL->last->next = p;
		VL->first->prev = p;
		VL->last = p;

	} else {

		p->next = p->prev = p;
		VL->first = p;
		VL->last = p;
	}
	VL->size++;
}

VertexList * imp_get_vertex_list_from_matrix(Matrix * Mat) {

	double * mat;
	int rows, columns;
	int r, c, _r, i;

	VertexList * VL;
	Vertex * p;


	_verify(Mat);

	VL = vertex_list_new();

	rows = Mat->rows;
	columns = Mat->columns;
	mat = Mat->data;

	for (r = 0, _r = r * columns; r < rows; r++, _r += columns) {
		for (c = 0; c < columns; c++) {
			i = _r + c;

			if (mat[i]) {

				p = imp_alloc(Vertex);

				p->idx = i;
				p->p.x = c;
				p->p.y = r;

				vertex_list_add(VL, p);
			}

		}
	}
	return VL;
}

void imp_sort_vertex_list(VertexList * VL) {

	Vertex * v;
	Vertex * *V;
	long int i;

	int vertex_compare(void * e1, void * e2) {
		

		Vertex ** v1 = e1;
		Vertex ** v2 = e2;
		
		//return (*v1)->idx - (*v2)->idx;

		if ((*v1)->p.x != (*v2)->p.x) return ((*v1)->p.x - (*v2)->p.x);
		else return ((*v1)->p.y - (*v2)->p.y);

	}

	_verify(VL);

	if (!VL->size) return;

	//Vertex * V[VL->size];

	V = (Vertex **) calloc(VL->size, sizeof (Vertex *));

	//V = imp_allocn(VL->size, Vertex *);

	v = VL->first;

	i = 0;
	do {
		V[i] = v;
		v = v->next;
		i++;
	} while (v != VL->first);

	gqsort(V, VL->size, sizeof (V[0]), vertex_compare);

	for (i = 1; i < VL->size; i++) {
		v = V[i - 1];
		v->next = V[i];
		v->next->prev = v;
	}

	VL->first = V[0];
	VL->last = V[VL->size - 1];

	VL->first->prev = VL->last;
	VL->last->next = VL->first;

	imp_free(V);
}

// <editor-fold defaultstate="collapsed" desc="Triangle Area Computation">

inline long int area2(Point2D A, Point2D B, Point2D C) {
	/**
	 *  Use the determinant form. a, b and c are points in R².
	 * 
	 *           | a.x  a.y  1 |
	 *  det(M) = | b.x  b.y  1 | = 2 * Area(a, b, c)
	 *           | c.x  c.y  1 |
	 */
	return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
}

inline float area(Point2D A, Point2D B, Point2D C) {
	/**
	 *  Use the determinant form. a, b and c are points in R².
	 * 
	 *           | a.x  a.y  1 |
	 *  det(M) = | b.x  b.y  1 | = 2 * Area(a, b, c)
	 *           | c.x  c.y  1 |
	 */
	return area2(A, B, C) / 2.0;
}
// </editor-fold>

// <editor-fold defaultstate="collapsed" desc="Polygon Area Computation">

inline long int area_poly2(VertexList VL) {
	long int area;
	Vertex * p;
	Vertex * a;

	p = VL.first;
	a = p->next;

	area = 0;
	do {
		area += area2(p->p, a->p, a->next->p);
		a = a->next;
	} while (a->next != VL.first);

	return area;
}

inline float area_poly(VertexList VL) {
	return area_poly2(VL) / 2.0;
}
// </editor-fold>

// <editor-fold defaultstate="collapsed" desc="Left verification">

boolean in_left(Point2D A, Point2D B, Point2D C) {
	return area2(A, B, C) > 0;
}

boolean in_left_on(Point2D A, Point2D B, Point2D C) {
	return area2(A, B, C) >= 0;
}// </editor-fold>

boolean is_collinear(Point2D A, Point2D B, Point2D C) {
	return area2(A, B, C) == 0;
}

// <editor-fold defaultstate="collapsed" desc="Right verification">

boolean in_right(Point2D A, Point2D B, Point2D C) {
	return area2(A, B, C) < 0;
}

boolean in_right_on(Point2D A, Point2D B, Point2D C) {
	return area2(A, B, C) <= 0;
}// </editor-fold>

// <editor-fold defaultstate="collapsed" desc="Intersection">

boolean is_intersect_prop(Point2D A, Point2D B, Point2D C, Point2D D) {
	if (is_collinear(A, B, C) ||
			is_collinear(A, B, D) ||
			is_collinear(C, D, A) ||
			is_collinear(C, D, B)) return FALSE;

	return XOR(in_left(A, B, C), in_left(A, B, D)) &&
			XOR(in_left(C, D, A), in_left(C, D, B));
}

boolean is_between(Point2D A, Point2D B, Point2D C) {
	if (!is_collinear(A, B, C)) return FALSE;

	if (A.x != B.x) return ( A.x <= C.x && C.x <= B.x) || (A.x >= C.x && C.x >= B.x);
	else return ( A.y <= C.y && C.y <= B.y) || (A.y >= C.y && C.y >= B.y);
}

boolean is_intersect(Point2D A, Point2D B, Point2D C, Point2D D) {
	if (is_intersect_prop(A, B, C, D)) return TRUE;
	else if (is_between(A, B, C) ||
			is_between(A, B, D) ||
			is_between(C, D, A) ||
			is_between(C, D, B)) return TRUE;
	else return FALSE;
}// </editor-fold>

VertexList * imp_get_convex_hull(VertexList * VL) {
	VertexList * HullUpper = NULL;
	VertexList * HullLower = NULL;
	Vertex * p1;
	Vertex * p2;
	Vertex * p3;
	Vertex * pi;
	Vertex * pnew;
	int left;

	long int i;

	HullUpper = vertex_list_new();
	HullLower = vertex_list_new();

	//imp_sort_vertex_list(VL);

	p1 = vertex_new_copy(VL->first);
	p2 = vertex_new_copy(VL->first->next);

	vertex_list_add(HullUpper, p1);
	vertex_list_add(HullUpper, p2);

	pi = VL->first->next;
	for (i = 2; i < VL->size; i++) {

		pi = pi->next;
		pnew = vertex_new_copy(pi);

		vertex_list_add(HullUpper, pnew);

		p3 = HullUpper->last;
		p2 = p3->prev;
		p1 = p2->prev;
		left = in_left(p1->p, p2->p, p3->p);

		while (HullUpper->size > 2 && left) {

			// delete p2;
			p1->next = p3;
			p3->prev = p1;
			vertex_delete(p2);

			p3 = HullUpper->last;
			p2 = p3->prev;
			p1 = p2->prev;

			left = in_left(p1->p, p2->p, p3->p);

		}
	}



	p1 = vertex_new_copy(VL->last);
	p2 = vertex_new_copy(VL->last->prev);

	vertex_list_add(HullLower, p1);
	vertex_list_add(HullLower, p2);

	pi = VL->last->prev;
	for (i = VL->size - 2; i > 0; i--) {

		pi = pi->prev;
		pnew = vertex_new_copy(pi);

		vertex_list_add(HullLower, pnew);

		p3 = HullLower->last;
		p2 = p3->prev;
		p1 = p2->prev;
		left = in_left(p1->p, p2->p, p3->p);

		while (HullLower->size > 2 && left) {

			// delete p2;
			p1->next = p3;
			p3->prev = p1;
			vertex_delete(p2);

			p3 = HullLower->last;
			p2 = p3->prev;
			p1 = p2->prev;

			left = in_left(p1->p, p2->p, p3->p);

		}
	}

	HullUpper->last->next = HullLower->first;
	HullLower->first->prev = HullUpper->last;

	HullUpper->first->prev = HullLower->last;
	HullLower->last->next = HullUpper->first;

	HullUpper->last = HullLower->last;


	imp_free(HullLower);

	return HullUpper;
}

void imp_draw_vertex_list(Image * Img, VertexList * VL) {

	Vertex * v1;
	Vertex * v2;

	v1 = VL->first;
	v2 = v1->next;

	do {
		image_draw_set_color(image_draw_color_new(RGB_RED));
		image_draw_line(Img, v1->p.x, v1->p.y, v2->p.x, v2->p.y);

		image_draw_set_color(image_draw_color_new(RGB_BLUE));
		image_draw_circle(Img, v1->p.x, v1->p.y, 4);

		v1 = v2;
		v2 = v2->next;
	} while (v2 != VL->first);
}

int diagonalie( VertexList * Poly, Vertex * a, Vertex * b ) {
	Vertex * c;
	Vertex * c1;
	
	/* For each edge  */
	
}